\begin{proof}[\textbf{Solution~\ref{ex:stream_ciphers:LFSR}}]
The recursion $s_{i+4} = s_{i+3} + s_{i}$ is immediately apparent 
as that specified by the diagram of the LFSR.  From this recursion, 
the given initial states expand to the following sequences:
\begin{center}
\begin{tabular}{cl}
{\rm a)} & {\tt 0110010001111010}\dots \\
{\rm b)} & {\tt 1110101100100011}\dots \\
{\rm c)} & {\tt 1010110010001111}\dots \\
{\rm d)} & {\tt 1100100011110101}\dots
\end{tabular}
\end{center}
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:stream_ciphers:show_definition_LFSR}}]
The data of a LFSR diagram, of a linear recurrences relation, and 
of a connection polynomial are equivalent --- they express the 
same information.  The connection polynomial $g(x) = \sum_j c_j x^j$
encodes the wiring of a LFSR which implements a recurrence relation.  
Thinking of $x^j$ as a shift operator acting on the sequence 
$s_0,s_1,s_2,\dots$, the behaviour of $g(x)$ in the product 
$g(x)s(x)$ (below) is precisely this recurrence relation.
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:stream_ciphers:LFSR_power_series}}]
The expression $f(x) = s(x)g(x)$ for a polynomial $f(x)$ of degree 
less than $n = \deg(g(x))$ is another equivalent formulation of the 
recurrence relation.  The initial $n$ coefficients of $s(x)$ are 
the entries of the shift register, and the $n$ coefficients of $f(x)$ 
is a linear combination of these coefficients.  
Although the coefficients of $f(x)$ are not equal to the initial 
state, for a nonsingular LFSR, the initial states are in bijection 
with the numerator polynomials $f(x)$. 
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:stream_ciphers:LFSR_construct_power_series}}]
The power series expansions of the first question are:
$$
\begin{array}{c@{\ }c@{\ }l@{\ }}
s(x) & = & x + x^2 + x^5 + x^9 + x^{10} 
           + x^{11} + x^{12} + x^{14} + \cdots \\
s(x) & = & 1 + x + x^2 + x^4 + x^6 + x^7 
           + x^{10} + x^{14} + x^{15} + \cdots \\
s(x) & = & 1 + x^2 + x^4 + x^5 + x^8 
           + x^{12} + x^{13} + x^{14} + x^{15} + \cdots \\
s(x) & = & 1 + x + x^4 + x^8 + x^9 + x^{10} 
           + x^{11} + x^{13} + x^{15} + \cdots
\end{array}
$$
Multiplying each through by the connection polynomial $g(x) 
= x^4 + x + 1$, we find the numerator polynomials for each of 
the sequences:
$$
\begin{array}{c@{\ }c@{\ }l@{\ }}
f(x) & = & x + x^3 \\
f(x) & = & 1 + x^3 \\
f(x) & = & 1 + x + x^2 + x^3 \\
f(x) & = & 1 + x^2 \\
\end{array}
$$
This verifies that the sequences output are consistent with their 
expected structure as coefficients of a rational power series. 
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:stream_ciphers:coefficient_sequence_draw_LFSR}}]
The polynomial $x^4 + x + 1$ is an irreducible polynomial, which is 
primitive.  The LFSR with this connection polynomial was given in 
the previous tutorial.  The primitivity follows since none of the 
sequences, computed last week, had a period shorter than $15$.  
The initial state corresponding to the polynomial $f(x) = x^3 + 1$
was the second given value $1110$ of the previous tutorial. 
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:stream_ciphers:compute_linear_complexity}}]
The linear complexity of the sequences $11$, $1011$, $10101$, 
$10110$, and $10011$ is $1$, $2$, $2$, $2$, and $3$.  The initial 
values follow from extending the sequences with period $1$, $3$,
$2$, and $3$, with connection polynomials $x+1$, $x^2+x+1$, $x^2+1$,
and $x^2+x+1$.  The third sequence can be extended to a sequence 
with period no better than $4$, so it generated by no LFSR of 
length $2$.  A possible connection polynomial is $x^4+1 = (x+1)^4$,
giving a LFSR of length $4$ which generates it.  However, the 
divisor $x^3+x^2+x+1 = (x+1)^3$ defines a recursion for a LFSR of 
length 3.  Hence the linear complexity for this sequence is $3$.
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:stream_ciphers:compute_first_8_terms_linear_complexity}}]
The first $8$ terms of the linear complexity profile for the 
sequence of the first question are:
$$
[ 1, 1, 1, 3, 3, 3, 4, 4 ].
$$
On the other hand, since the sequence is generated by a LFSR of 
length $4$ we know that the full infinite sequence becomes constant 
at $4$. 
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:stream_ciphers:practice_encode_decode_LFSR}}]
The encoding and decoding member functions associated with a LFSR are 
just a wrapper around \verb!binary_encoding! and \verb!binary_decoding!:
%\input{code/solution09.1.m}
\input{code/solution09.1.sage}
We verify using that \verb!binary_decoding! that the binary string also 
returns the ASCII message:
%\input{code/solution09.2.m}
\input{code/solution09.2.sage} 
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:stream_ciphers:inverse_equal_itself}}]
Since LFSR ciphertext is the bitsum of plaintext with a keystream, 
a subsequent bitsum with the same keystream gives the original plaintext:
$$
c_i + s_i = (m_i + s_i) + s_i = m_i + (s_i + s_i) = m_i + 0 = m_i,
$$
Therefore enciphering map is equal to deciphering map; in particular, 
the enciphering and deciphering keys are the same. 
\end{proof}
